package cn.zifangsky.tree.binarytree;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.stack.LinkStack;

public class BinaryTreeNodeOperations {
	
	/**
	 * 前序遍历
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void preOrder(BinaryTreeNode<Integer> root){
		if(root != null){
			System.out.print(root.getData() + " ");
			preOrder(root.getLeft()); //遍历左子树
			preOrder(root.getRight()); //遍历右子树
		}
	}
	
	/**
	 * 非递归前序遍历：使用栈辅助操作
	 * 思路：1.将当前节点加入到栈中，访问当前节点的值，然后遍历并访问它所有左孩子节点，同时将这些节点入栈
	 *     2.依次出栈，并访问该节点的右孩子节点
	 *     3.循环上面两个步骤
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void preOrderByStack(BinaryTreeNode<Integer> root){
		LinkStack<BinaryTreeNode<Integer>> stack = new LinkStack<>();

		while (true) {
			while (root != null) {
				stack.push(root);
				System.out.print(root.getData() + " ");
				root = root.getLeft();
			}
			
			if(stack.isEmpty()){
				break;
			}	
			
			BinaryTreeNode<Integer> temp = stack.pop();
			
			root = temp.getRight();			
		}
	}
	
	/**
	 * 中序遍历
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void InOrder(BinaryTreeNode<Integer> root){
		if(root != null){
			InOrder(root.getLeft()); //遍历左子树
			System.out.print(root.getData() + " ");
			InOrder(root.getRight()); //遍历右子树
		}
	}
	
	/**
	 * 非递归中序遍历：使用栈辅助操作
	 * 思路：1.将当前节点加入到栈中，然后遍历它所有左孩子节点，同时将这些节点入栈
	 *     2.依次出栈，访问当前节点的值，并遍历该节点的右孩子节点
	 *     3.循环上面两个步骤
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void InOrderByStack(BinaryTreeNode<Integer> root){
		LinkStack<BinaryTreeNode<Integer>> stack = new LinkStack<>();

		while (true) {
			while (root != null) {
				stack.push(root);
				root = root.getLeft();
			}
			
			if(stack.isEmpty()){
				break;
			}	
			
			BinaryTreeNode<Integer> temp = stack.pop();
			System.out.print(temp.getData() + " ");
			
			root = temp.getRight();			
		}
	}
	
	/**
	 * 后序遍历
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void postOrder(BinaryTreeNode<Integer> root){
		if(root != null){
			postOrder(root.getLeft()); //遍历左子树
			postOrder(root.getRight()); //遍历右子树
			System.out.print(root.getData() + " ");
		}
	}
	
	/**
	 * 非递归后序遍历：使用栈辅助操作
	 * 思路：1.将当前节点入栈两次，然后遍历它所有左孩子节点，同时将这些节点也入栈两次
	 *     2.依次出栈，判断当前出栈的节点与当前栈中的栈顶节点值时候相等
	 *     3.如果相等，则说明这是这个节点第一次出栈（PS：第一次被遍历），此时需要遍历该节点的右孩子节点；
	 *       如果不相等，则说明这是这个节点第二次出栈（PS：第二次被遍历），那么访问当前节点的值
	 *     4.循环上面步骤
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void postOrderByStack(BinaryTreeNode<Integer> root){
		LinkStack<BinaryTreeNode<Integer>> stack = new LinkStack<>();

		while (true) {
			while (root != null) {
				stack.push(root);
				stack.push(root); //压入两次
				root = root.getLeft();
			}
			
			if(stack.isEmpty()){
				break;
			}
			
			BinaryTreeNode<Integer> temp = stack.pop();
			BinaryTreeNode<Integer> topNode = null; //当前栈的栈顶节点
			if(!stack.isEmpty()){
				topNode = stack.top();
			}
			
			/**
			 * 如果节点temp与当前栈的栈顶节点相同，则说明这是第一次遍历，需要把它的右子树入栈
			 * 如果不相同，则说明是第二次遍历，访问节点temp
			 */
			if(topNode != null && temp == topNode){
				root = temp.getRight();
			}else{
				System.out.print(temp.getData() + " ");
			}
			
		}
	}
	
	/**
	 * 层次遍历：使用队列辅助操作
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void levelOrder(BinaryTreeNode<Integer> root){
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.push(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> temp = queue.pop();
			System.out.print(temp.getData() + " ");
			
			if(temp.getLeft() != null){
				queue.push(temp.getLeft());
			}
			if(temp.getRight() != null){
				queue.push(temp.getRight());
			}
		}
	
	}
	
	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(1); //根节点
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<Integer>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<Integer>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.push(tmpNode1);
			queue.push(tmpNode2);
		}
		
		/**
		 * 前序遍历：
		 * 1 2 4 5 8 9 3 6 7
		 */
		System.out.println("前序遍历：");
		preOrder(root);
		System.out.println();
		preOrderByStack(root);
		System.out.println();

		/**
		 * 中序遍历：
		 * 4 2 8 5 9 1 6 3 7
		 */
		System.out.println("中序遍历：");
		InOrder(root);
		System.out.println();
		InOrderByStack(root);
		System.out.println();
		
		
		/**
		 * 后序遍历：
		 * 4 8 9 5 2 6 7 3 1
		 */
		System.out.println("后序遍历：");
		postOrder(root);
		System.out.println();
		postOrderByStack(root);
		System.out.println();
		
		/**
		 * 层次遍历：
		 * 1 2 3 4 5 6 7 8 9
		 */
		System.out.println("层次遍历：");
		levelOrder(root);

	}

}
